
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0300
 * @Author : WangRuoyu 
 * @Date : 2023/5/26 16:23
 */

#include "iostream"
#include "vector"

using namespace std;

class Solution {
public:
    /**
    * O(nlogn) O(n)
    */
    int lengthOfLIS(vector<int> &nums) {
        if (nums.empty()) return 0;
        vector<int> res;
        res.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > res[res.size() - 1]) {
                res.push_back(nums[i]);
                continue;
            }
            if (nums[i] <= res[0]) {
                res[0] = nums[i];
                continue;
            }
            int l = 0;
            int r = res.size() - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (res[mid] < nums[i]) l = mid;
                else r = mid - 1;
            }
            res[l + 1] = nums[i];
        }
        return res.size();
    }

    /**
     * O(n^2) O(n)
     */
//    int lengthOfLIS(vector<int> &nums) {
//        int f[nums.size()];
//        int res = 0;
//        for (int i = 0; i < nums.size(); ++i) {
//            f[i] = 1;
//            int tmp = 0;
//            for (int j = 0; j < i; ++j) {
//                if (nums[i] > nums[j]) tmp = max(tmp, f[j]);
//            }
//            f[i] += tmp;
//            res = max(res, f[i]);
//        }
//        return res;
//    }
};

int main() {
    Solution sl;
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    printf("%d", sl.lengthOfLIS(nums));
    return 0;
}